矩阵最长递增路径

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#
class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        # write code here
        directions = [[0,1], [0,-1], [1,0], [-1,0]]
        n = len(matrix)
        m = len(matrix[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]

        def dfs(x, y):
            if dp[x][y]>0:
                return dp[x][y]
            res = 1
            for dx, dy in directions:
                nx = x+dx
                ny = y+dy
                if 0<=nx<n and 0<=ny<m and matrix[nx][ny] > matrix[x][y]:
                    res = max(res, dfs(nx, ny)+1)
            dp[x][y] = res
            return res
                    
        max_depth = float('-inf')   
        for i in range(n):
            for j in range(m):
                    max_depth = max(max_depth, dfs(i, j))
        return max_depth

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#
class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        # write code here
        row = len(matrix) 
        col = len(matrix[0]) 
        
        dp = [[-1]*col for _ in range(row)] 
        
        def dfs(grid, i, j): 
            if dp[i][j] == -1: 
                
                step = 1 
                for x, y in [(-1,0), (1,0), (0, 1), (0, -1)]: 
                    temp_i = i + x 
                    temp_j = j + y 
                    
                    if 0 <= temp_i < row and 0 <= temp_j < col and grid[temp_i][temp_j] > grid[i][j]: 
                        step = max(step, dfs(grid, temp_i, temp_j) + 1) 
                dp[i][j] = step 
                return step 
            else: 
                return dp[i][j] 
            
                    
        
        res = 0 
        for i in range(row): 
            for j in range(col): 
                if dp[-1][-1] == -1: 
                    res = max(res, dfs(matrix, i, j)) 
        return res 
    
                
        

        

class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        # write code here
        res = 0  # 记录结果
        trace = {}  # 记录已经递归过的点
        # 遍历以i,j为初始点的最长路径
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                # 如果（i，j）在前面的点的路径上，那以i，j为初始点的最长路径可以查表
                if (i, j) in trace.keys():
                    length = trace[(i, j)]
                # 否则调用dfs求最长路径
                else:
                    length = self.dfs(matrix, -1, i, j, trace)
                res = max(res, length)
        return res  
    
    def dfs(self, matrix, num, i, j, trace):
        # 若(i,j)在界外，或者它比前一个数小，返回0
        if i < 0&nbs***bsp;i >= len(matrix)&nbs***bsp;j < 0&nbs***bsp;j >= len(matrix)&nbs***bsp;matrix[i][j] <= num:
            return 0
        # 否则， 遍历（i，j）的四个邻位
        d = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
        length = 0
        for direct in d:
            # 如果某邻位已在表中，只要邻位元素大于该位置，便查表
            if direct in trace.keys() and matrix[direct[0]][direct[1]] > matrix[i][j]:
                length = max(length, trace[direct]+1)
            # 否则进入dfs递归
            else:
                res = self.dfs(matrix, matrix[i][j], direct[0], direct[1], trace)
                length = max(length, res+1)
        trace[(i, j)] = length    # 将以该位置为起点的最长路径记录在表
        return length

动态规划， 辅助空间dp储存该点的最大递增路径数
时间复杂度：O(mn) 空间复杂度：O(mn)

class Solution:
    global n,m, dirs
    dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    def dfs(self, i, j, matrix, dp):
        if dp[i][j] != 0:
            return dp[i][j]
        dp[i][j] += 1
        for k in range(4):
            nexti = i + dirs[k][0]
            nextj = j + dirs[k][1]
            if nexti < n and nexti >= 0 and nextj < m and nextj >= 0 and matrix[nexti][nextj] > matrix[i][j]:
                dp[i][j] = max(dp[i][j], self.dfs(nexti, nextj, matrix, dp) + 1)
        return dp[i][j]

    def solve(self , matrix: List[List[int]]) -> int:
        global n,m
        res = 0
        n = len(matrix)
        m = len(matrix[0])
        if n == 0 or m == 0:
            return 0
        dp = [[0 for j in range(m)] for i in range(n)]
        for i in range(n):
            for j in range(m):
                res = max(res, self.dfs(i, j, matrix, dp))
        return res

class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        # write code here
        '''
        使用record记录以某个单元格为 起点 的最大路径.
        '''
        def dfs(row, col, record):
            if record[row][col] != 0: return record[row][col]
            record[row][col] = 1 # 当前单元格标致为1.
            up = down = left = right = 1

            if row - 1 >= 0 and matrix[row - 1][col] > matrix[row][col]:
                up = dfs(row - 1, col, record) + 1    # 上
            if row + 1 < len(matrix) and matrix[row + 1][col] > matrix[row][col]:
                down = dfs(row + 1, col, record) + 1  # 下
            if col - 1 >= 0 and matrix[row][col - 1] > matrix[row][col]:
                left = dfs(row, col - 1, record) + 1  # 左
            if col + 1 < len(matrix[0]) and matrix[row][col + 1] > matrix[row][col]:
                right = dfs(row, col + 1, record) + 1 # 右

            cur_longest = max(up, down, left, right)
            record[row][col] = cur_longest
            return cur_longest

        longest = 1
        record = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                longest = max(longest, dfs(row, col, record))
        return longest

class Solution:
    def __init__(self):
        self.res = 0
        
    def solve(self , matrix ):
        # write code here
        if len(matrix) == 0&nbs***bsp;len(matrix[0]) == 0:
            return 0
        m, n = len(matrix), len(matrix[0])
        for i in range(m):
            for j in range(n):
                self.dfs(matrix, m, n, i, j, 0, -1)
        return self.res
    
    def dfs(self, matrix, m, n, i, j, cur_len, pre):
        if i<0&nbs***bsp;j<0&nbs***bsp;i>=m&nbs***bsp;j>=n&nbs***bsp;matrix[i][j]<=pre:
            if cur_len > self.res:
                self.res = cur_len
            return
        self.dfs(matrix, m, n, i + 1, j, cur_len + 1, matrix[i][j])
        self.dfs(matrix, m, n, i - 1, j, cur_len + 1, matrix[i][j])
        self.dfs(matrix, m, n, i, j + 1, cur_len + 1, matrix[i][j])
        self.dfs(matrix, m, n, i, j - 1, cur_len + 1, matrix[i][j])